Path exploration is an intrinsic phenomenon associated to any path-vector routing protocol. Many efforts have been spent over the last decade to quantify and mitigate its detrimental effects. There are basically three classes of approaches to mitigate its effects:    root cause notification to perform an informed AS-path selection or to annotate the AS paths with additional “path dependency” information;    shorten MRAI time to fasten convergence: however, decreasing the MRAI below a certain threshold leads to adversary effects in terms of convergence time and number of BGP updates, and thus exacerbates path exploration phenomenon.    Backup/Multi AS-path (increase AS-Path diversity): this solution affects the number of RIB states to be maintained and thus results in adversary effects on routing scalability.